package designpatterns.strategy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;


public class MergeSort extends GeneralSort {
	@Override
	public ArrayList<Integer> sort(ArrayList<Integer> data) {
		
		List<Integer> list = data;
										
		ExecTime = System.currentTimeMillis();
		
		list = mergeSort(list);
						
		ExecTime = System.currentTimeMillis() - ExecTime;
		
		internalData = list.toArray(new Integer[list.size()]);
				
		return new ArrayList <Integer> (list);
	}

	private List<Integer> mergeSort(List<Integer> list) {
		if (list.size() <= 1) {
			return list;
		} else {
			int middle = list.size() / 2;
			
			List <Integer> leftList = list.subList(0, middle);
			List <Integer> rightList = list.subList(middle, list.size());
			
			leftList = mergeSort(leftList);
			rightList = mergeSort(rightList);
			
			List <Integer> sortedList = new ArrayList<Integer>();
			
			Iterator<Integer> leftIterator = leftList.iterator();
			Iterator<Integer> rightIterator = rightList.iterator();
			
			Integer leftBuffer = null;
			Integer rightBuffer = null;
					
			while (leftIterator.hasNext() || rightIterator.hasNext()) {
				if (leftBuffer == null && leftIterator.hasNext()) {
					leftBuffer = leftIterator.next();
				}
				if (rightBuffer == null && rightIterator.hasNext()) {
					rightBuffer = rightIterator.next();
				}
				
				if (leftBuffer == null) {
					sortedList.add(rightBuffer);
					rightBuffer = null;
					continue;
				}

				if (rightBuffer == null) {
					sortedList.add(leftBuffer);
					rightBuffer = null;
					continue;
				}
				
				if (leftBuffer < rightBuffer) {
					sortedList.add(leftBuffer);
					leftBuffer = null;
				} else {
					sortedList.add(rightBuffer);
					rightBuffer = null;
				}
			}
			
			if (leftBuffer == null) {
				sortedList.add(rightBuffer);
			} else {
				sortedList.add(leftBuffer);
			}

			
			return sortedList;
		}
    }

	@Override
    public String getName() {
	    // TODO Auto-generated method stub
	    return "MergeSort " + isSorted();
    }

}
